// 给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出 null。

// 方法一：遍历这个链表，将结点存入数组中，给每次加入的结点做一个判断：是否这个结点已经保存在数组，如果保存过，说明这个结点就是环的入口节点

/*function ListNode(x){
    this.val = x;
    this.next = null;
}*/
// 遍历对比法
function EntryNodeOfLoop(pHead) {
  // write code here
  if (!pHead) return null;
  let arr = [];
  let node = pHead;
  while (node) {
    if (arr.includes(node)) {
      return node;
    }
    arr.push(node);
    node = node.next;
  }
  return null;
}

// 方法3 牛客偷的方法,访问过的节点设置一个flag,通过flag判断是否第二次访问(也就是环的起点)
function EntryNodeOfLoop(pHead) {
  while (pHead !== null) {
    if (pHead.flag) {
      return pHead;
    } else {
      pHead.flag = true;
      pHead = pHead.next;
    }
  }
  return null;
}

// 方法3 快慢指针
/*function ListNode(x){
    this.val = x;
    this.next = null;
}*/

function EntryNodeOfLoop(pHead) {
  // write code here
  if (pHead == null) {
    return null;
  }
  if (pHead.next == null) {
    return null;
  }
  let fast = pHead;
  let slow = pHead;
  while (slow != null && fast.next != null) {
    slow = slow.next;
    fast = fast.next.next;
    if (fast == slow) break;
  }

  let p1 = slow;
  let p2 = pHead;
  while (p1 != p2) {
    p1 = p1.next;
    p2 = p2.next;
  }
  return p1;
}
